package com.xjj.dbfs;

import java.util.*;

public class M0433MinimumGeneticMutation {

    public int minMutation(String start, String end, String[] bank) {
        // 最小,用bfs,4-1种变化方向,8个位置,24种新状态
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
        char[] keys = {'A', 'C', 'G', 'T'};
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        int depth = 0;
        // 要加个访问过的集合,不然会一直往复循环下去
        Set<String> visited = new HashSet<>();
        visited.add(start);
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 遍历一层的字符串
            for (int i = 0; i < size; i++) {
                // 出当前层的队列
                String currentStr = queue.poll();
                if (currentStr.equals(end)) {
                    return depth;
                }
                // 遍历八个位置
                for (int k = 0; k < start.length(); k++) {
                    char[] currentChars = currentStr.toCharArray();
                    char currentChar = currentChars[k];
                    // 四种变化
                    for (int j = 0; j < keys.length; j++) {
                        // k位置的字符变了
                        if (currentChar == keys[j]) {
                            continue;
                        } else {
                            currentChars[k] = keys[j];
                        }
                        String newStr = new String(currentChars);
                        // System.out.println(newStr);
                        if (bankSet.contains(newStr) && !visited.contains(newStr)) {
                            // 符合可以直接返回,少算一层
                            if (newStr.equals(end)) {
                                return depth + 1;
                            }
                            // 新一层加进队列
                            queue.add(newStr);
                        }
                        visited.add(newStr);
                    }
                }
            }
            // 本层数据都遍历完,层数+1
            depth++;
        }
        return -1;
    }
}
